743. Network Delay Time

#Algorithm #Algorithm_Dijkstra #Algorithm_Graph #DataStructure-Priority_Queue #DataStructure-Heap

743. Network Delay Time

1. 문제

1-1. 원문

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Example 2:
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Example 3:
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

Constraints:

1-2. 내용 번역

[시작 노드, 도착 노드, 걸리는 시간]배열을 하나의 아이템으로 가지는 배열 time이 존재한다. 노드 k에서 시작해서 모든 노드들에 도착하기 까지 걸리는 최소 시간을 구하여라. 만약 하나의 노드라도 도착할 수 없으면(끊어져 있으면) -1을 리턴해라.


2. 문제 이해

2-1. 내용 이해

'노드 k에서 시작해서 모든 노드들에 도착하기 까지 걸리는 최소 시간'이란 노드와 노드 사이를 병렬적으로 이동한다고 생각해야 이해가 된다. 이것을 바꿔서 말하면 '각 도착 노드에 도착했을 때 산출된 결과값들 중에 최대 값을 구해라'라고 이해할 수도 있겠다.

2-2. 접근법 생각

최소 경로? 출발 노드가 있고 모든 노드가 도착노드가 된다? 다익스트라로 풀어야 겠네.

2-3. 적용한 풀이

Dijkstra


3. 구현

class Solution {
    val MAX_VALUE = 700000

    fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {
        val graphMap: MutableMap<Int, MutableSet<Node>> = mutableMapOf()
        val visitedNode: MutableSet<Int> = mutableSetOf()
        val timeTakenArr: IntArray = IntArray(n+1){MAX_VALUE}
        val pq: PriorityQueue<Node> = PriorityQueue { o1, o2 -> if (o1.time > o2.time) 1 else -1} // 오름차순 정렬

        for(time in times) {
	        // 유향 그래프
            (graphMap.getOrPut(time[0]){mutableSetOf()}).add(Node(time[1], time[2]))
        }
        
        pq.offer(Node(k, 0))
        timeTakenArr[0] = 0 // 노드의 라벨이 1부터 시작하기 때문에 인덱스0은 사용하지 않으므로 무시될 수 있는 값 대입
        timeTakenArr[k] = 0

        while(pq.isNotEmpty()) {
            val curNode = pq.poll()
            val curTime = curNode.time

            if (visitedNode.contains(curNode.edge).not()) {
                visitedNode.add(curNode.edge)

                graphMap.getOrDefault(curNode.edge, mutableSetOf()).forEach { (edge, time) -> 
                    if (visitedNode.contains(edge).not()) {
                        timeTakenArr[edge] = Math.min(timeTakenArr[edge], curTime+time)
                        pq.offer(Node(edge, timeTakenArr[edge]))
                    }
                }
            }
        }

        val maxTime: Int? = timeTakenArr.maxOrNull()

        return if (maxTime == null || maxTime == MAX_VALUE) -1 else maxTime
    }
}

data class Node(val edge: Int, val time: Int)